﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace BS8
{
	TEST_CLASS(P3611)
	{
		//P3611 [USACO17JAN] Cow Dance Show S
		class Solution {
		public:
			int Ans(int T,vector<int>&a ) {
				const int N = a.size();
				auto Check = [&](int mid) {
					priority_queue<int, vector<int>, greater<int>> maxHeap;
					int i = 0;
					for (; i < mid; i++) {
						maxHeap.emplace(a[i]);
					}
					while (maxHeap.size()) {
						if (maxHeap.top() > T) { return false; }
						if (i < N) {
							maxHeap.emplace(maxHeap.top() + a[i]); i++;
						}
						maxHeap.pop();
					}
					return true;
				};
				return CBinarySearch<int>(1, N).FindFrist(Check);
			}
		};
	public:
		int T;
		vector<int> a;
		TEST_METHOD(TestMethod11)
		{
			T = 8, a = { 4,7,8,6,4 };
			auto res = Solution().Ans(T,a);
			AssertEx(4, res);
		}

	};

	TEST_CLASS(P10237)
	{
		//【二分查找 寻找首端】P10237 [yLCPC2024] E. Latent Kindom|普及+
		class Solution {
		public:
			vector<long long> Ans(vector<vector<long long>>& a, vector<pair<int,int>>& que) {
				const int N = a.size();
				vector<long long > vSort;
				for (auto& v : a) {
					sort(v.begin(), v.end());
					vSort.insert(vSort.end(), v.begin(), v.end());
				}
				sort(vSort.begin(), vSort.end());
				vSort.erase(std::unique(vSort.begin(), vSort.end()), vSort.end());
				auto LessEqual = [&](int i, int j, long long x) {
					const int c1 = upper_bound(a[i].begin() , a[i].end(), x) - a[i].begin();
					const int c2 = upper_bound(a[j].begin() , a[j].end(), x) - a[j].begin();
					return c1 + c2;
				};
				vector<long long> ans;
				for (auto [i, j] : que) {
					i--, j--;
					const auto c = (a[i].size() + a[j].size() + 1)/2;
					auto Check = [&](int mid) {						
						return LessEqual(i,j,vSort[mid]) >= c ;
					};
					ans.emplace_back(vSort[CBinarySearch<int>(0,vSort.size()-1).FindFrist(Check)]);
				}				
				return ans;
			}
		};
	public:
		vector<vector<long long>> a;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod11)
		{
			a = { {1},{2,3},{4,5,6} },que = { {1,2},{1,3},{2,3} };
			auto res = Solution().Ans(a,que);
			AssertEx({ 2,4,4 }, res);
		}

	};

	TEST_CLASS(LC220)
	{
		//【二分查找】【z型搜索】LeetCode240:搜索二维矩阵
		class Solution {
		public:
			bool searchMatrix(vector<vector<int>>& matrix, int target) {
				m_r = matrix.size();
				m_c = matrix.front().size();
				int r = 0, c = m_c - 1;
				while ((r < m_r) && (c >= 0)) {
					if (target == matrix[r][c]) {
						return true;
					}
					if (matrix[r][c] > target) {
						c--;
					}
					else {
						r++;
					}
				}
				return false;
			}
			int m_r, m_c;
		};
	public:
		vector<vector<int>> matrix;
		int target;
		TEST_METHOD(TestMethod11)
		{
			Solution slu;
			matrix = { {1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30} };
			target = 5;
			auto res = slu.searchMatrix(matrix, target);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod12)
		{
			Solution slu;
			matrix = { {1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30} };
			target = 20;
			auto res = slu.searchMatrix(matrix, target);
			AssertEx(false, res);
		}
	};

	TEST_CLASS(P3718)
	{
		//【堆 优先队列】P3718 [AHOI2017初中组] alter|普及+
		class Solution {
		public:
			int Ans(vector<char>& a, const int K) {
				const int N = a.size();
				int preIndex = 0;
				vector<int> vLen;
				for (int i = 1; i < N; i++) {
					if (a[i] == a[preIndex]) { continue; }
					vLen.emplace_back(i - preIndex);
					preIndex = i;
				}
				vLen.emplace_back(N - preIndex);
				auto Check = [&](int mid) {
					int cnt = 0;
					for (const auto& i : vLen) {
						cnt += i / (mid + 1);
					}
					return cnt <= K;
				};
				const int ans = CBinarySearch<int>(1, N).FindFrist(Check);
				if (1 == ans) {
					auto Cnt = [&](char ch) {
						int cnt = 0;
						for (int i = 0; i < N; i++) {
							cnt += (i % 2) ^ (a[i] == ch);
						}
						return cnt;
					};
					if (min(Cnt('N'), Cnt('F')) > K) { return 2; }
				}
				return ans;
			}
		};
	public:
		vector<char> a; int k;
		TEST_METHOD(TestMethod11)
		{
			k = 1, a = { 'N','N','N','F','F','N','N','N' };
			auto res = Solution().Ans(a, k);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			k = 1, a = { 'N','F','F','N' };
			auto res = Solution().Ans(a, k);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			k = 2, a = { 'N','F','F','N' };
			auto res = Solution().Ans(a, k);
			AssertEx(1, res);
		}
	};

	TEST_CLASS(P6004)
	{
		//P6004 [USACO20JAN] Wormhole Sort S
		class Solution {
		public:
			int Ans(vector<int>& vp, vector<tuple<int,int,int>>& edge) {
				const int N = vp.size();
				CUnionFind uf(N);
				for (int i = 0; i < N; i++) {
					uf.Union( vp[i] - 1,i);
				}
				if (uf.GetConnetRegionCount() == N) { return -1; }
				auto m = uf.GetNodeOfRegion();
				auto Check = [&](int mid) {
					CUnionFind uf2(N);
					for (const auto& [u, v, w] : edge) {
						if (w < mid) { continue; }
						uf2.Union(u-1, v-1);
					}
					for (const auto& [tmp, v] : m) {
						for (int i = 1; i < v.size(); i++) {
							if (!uf2.IsConnect(v[0], v[i])) { return false; }
						}
					}
					return true;
				};
				return CBinarySearch<int>(1,1e9).FindEnd(Check);
			}
		};
	public:
		vector<int> vp			;
		vector<tuple<int, int, int>> edge;
		TEST_METHOD(TestMethod11)
		{
			 vp = { 3,2,1,4 },edge = { {1,2,9},{1,3,7},{2,3,10},{2,4,3} };
			auto res = Solution().Ans(vp,edge);
			AssertEx(9, res);
		}
		TEST_METHOD(TestMethod12)
		{
			vp = { 1,2,3,4 }, edge = { {4,2,13} };
			auto res = Solution().Ans(vp, edge);
			AssertEx(-1, res);
		}
	};

	TEST_CLASS(P6172)
	{
		//【二分查找 树状数组 差分数组 离散化 】P6172 [USACO16FEB] Load Balancing P|普及+
		class Solution {
		public:
			int Ans(vector<pair<int, int>>& pts) {
				const int N = pts.size();
				sort(pts.begin(), pts.end());
				vector<int> ys;
				for (const auto& [x, y] : pts) {
					ys.emplace_back(y);
				}
				CDiscretize dis(ys);
				for (auto& [x, y] : pts) {
					y = dis[y];
				}		
				const int M = dis.size();
				CTreeArr<int> diff1(M), diff2(M);	
				for (const auto& [x, y] : pts) {
					diff2.Add(y, 1);
				}
				int ans = INT_MAX / 2;
				for (int i = 0; i < N; i++) {	
					auto Check = [&](int mid) {
						const int M1 = diff1.Sum(mid);
						const int M2 = diff2.Sum(mid);
						const int M3 = i - M1;
						const int M4 = (N - i) - M2;
						return max(M1, M2) > max(M3, M4);
					};
					auto CalMax = [&](int mid) {
						const int M1 = diff1.Sum(mid);
						const int M2 = diff2.Sum(mid);
						const int M3 = i - M1;
						const int M4 = (N - i) - M2;
						return max(max(M1, M2), max(M3, M4));
					};
					int b = CBinarySearch<int>(0, M - 1).FindFrist(Check);
					ans = min(ans, CalMax(b));
					ans = min(ans, CalMax(b - 1));
					diff1.Add(pts[i].second, 1);
					diff2.Add(pts[i].second, -1);
					while ((i + 1 < N) && (pts[i].first == pts[i + 1].first)) {
						i++;
						diff1.Add(pts[i].second, 1);
						diff2.Add(pts[i].second, -1);						
					}					
					
				}
				return ans;
			}
		};
	public:
		vector<pair<int, int>> pts;
		TEST_METHOD(TestMethod1)
		{
			pts = { {7,3},{5,5},{7,13},{3,1},{11,7},{5,3},{9,1} };
			auto res = Solution().Ans(pts);
			AssertEx(2, res);
		}
	};

	TEST_CLASS(P6733)
	{
		//【二分查找 双指针】P6733 「Wdsr-2」间歇泉|普及+
		class Solution {
		public:
			long long Ans(int K, vector<pair<int, long long>>& vc) {
				const int N = vc.size();
				for (auto& [v, c] : vc) { c *= 1000; }
				auto Cmp = [&](const pair<int, int>& pr, long long mid) {return (long long)pr.first * pr.second - pr.first * mid; };
				auto Check = [&](long long mid) {
					sort(vc.begin(), vc.end(), [&](const pair<int, int>& pr1, const pair<int, int>& pr2) {
						return Cmp(pr1, mid) < Cmp(pr2, mid);  });
					vector<long long> cmps(N);
					for (int i = 0; i < N; i++) {
						cmps[i] = Cmp(vc[i], mid);
					}
					long long cnt = 0;
					for (const auto& pr : vc) {
						const auto needMoreEqual = -Cmp(pr, mid);
						auto it = lower_bound(cmps.begin(), cmps.end(), needMoreEqual);
						cnt += cmps.end() - it;
						cnt -= (-needMoreEqual >= needMoreEqual);//不能和自己混合
					}
					return cnt/2 >= K;
				};
				return CBinarySearch<long long>(1, 1e12).FindEnd(Check);
			}
		};
	public:
		int K;
		vector<pair<int, long long>> vc;
		TEST_METHOD(TestMethod1)
		{
			K = 1, vc = { {1,5},{4,2},{5,3},{2,3},{1,4} };
			auto res = Solution().Ans(K,vc);
			AssertEx(4500LL, res);
		}
	};

	TEST_CLASS(P7971)
	{
		//【二分 寻找尾端】P7971 [KSN2021] Colouring Balls|普及+
		class IQuery
		{
		public:
			virtual int Query(int left, int r) = 0;
		};
		class Solution {
		public:
			vector<int> Ans(int T ,const int N, IQuery& que) {
				if (T <= 2) { return AnsT12(N, que); }
				if( T <= 4) { return AnsT34(N, que); }
				int cnt = 0;
				vector<int> ans(N), colorToEndIndex(N + 1, -1);
				vector<int> endIndex;
				auto Add = [&](int index, int color) {
					vector<int> tmp = { index };
					for (const auto& i : endIndex) {
						if (i == colorToEndIndex[color]) { continue; }
						tmp.emplace_back(i);
					}
					sort(tmp.begin(), tmp.end());
					endIndex.swap(tmp);
					colorToEndIndex[color] = index;
				};
				for (int i = 0; i < N; i++) {
					int iNew = que.Query(1, i + 1);
					if (iNew > cnt) {
						ans[i] = ++cnt;
						Add(i + 1, ans[i]);
						continue;
					}
					auto Check = [&](int mid) {
						const int cnt = endIndex.end() - lower_bound(endIndex.begin(), endIndex.end(), mid);
						return cnt == que.Query(mid, i + 1);
					};
					ans[i] = ans[CBinarySearch(1, i).FindEnd(Check) - 1];
					Add(i + 1, ans[i]);
				}
				return ans;
			}
			vector<int> AnsT34(const int N, IQuery& que)
			{
				int cnt = 0;
				vector<int> ans(N), colorToEndIndex(N + 1, -1);
				vector<int> endIndex;
				auto Add = [&](int index, int color) {
					vector<int> tmp = { index };
					for (const auto& i : endIndex) {
						if (i == colorToEndIndex[color]) { continue; }
						tmp.emplace_back(i);
					}
					sort(tmp.begin(), tmp.end());
					endIndex.swap(tmp);
					colorToEndIndex[color] = index;
				};
				ans[0] = ++cnt;
				Add(1, 1);
				for (int i = 1; i < N; i++) {
					auto Check = [&](int mid) {
						const int cnt = endIndex.size() - mid;
						return cnt == que.Query(endIndex[mid], i + 1);
					};
					int ci = CBinarySearch<int>(0, endIndex.size() - 1).FindEnd(Check);
					if ((4 == cnt)|| Check(ci)) {
						ans[i] = ans[endIndex[ci] - 1];
					}
					else {
						ans[i] = ++cnt;
					}
					Add(i + 1, ans[i]);
				}
				return ans;
			}
			vector<int> AnsT12(const int N, IQuery& que) {
				int cnt = 0;
				vector<int> ans(N);
				for (int i = 0; i < N; i++) {
					int iNew = que.Query(1, i + 1);
					if (iNew > cnt) {
						ans[i] = ++cnt; continue;
					}					
					ans[i] =ans[i-1];
				}
				return ans;
			}
		};
	public:
	
		class CQuery : public IQuery {
		public:
		virtual	int Query(int left, int r)  {
				m_cnt++;
				left--, r--;
				unordered_set<int> s;
				for (int i = left; i <= r; i++) {
					s.emplace(m_data[i]);
				}
				return s.size();
			}
			vector<int> m_data;
			int m_cnt;
		};
		int K;
		vector<pair<int, long long>> vc;
		TEST_METHOD(TestMethod11)
		{
			CQuery que;
			que.m_data = { 1,1,2,1,1 };
			auto res = Solution().Ans(100,que.m_data.size(), que);
			AssertEx(que.m_data, res);
		}
		TEST_METHOD(TestMethod12)
		{
			CQuery que;
			que.m_data = { 1,1,1,2,2 };
			auto res = Solution().Ans(100,que.m_data.size(), que);
			AssertEx(que.m_data, res);
		}
		TEST_METHOD(TestMethod13)
		{
			CQuery que;
			que.m_data = { 1,2,3,4,5,6 };
			auto res = Solution().Ans(100,que.m_data.size(), que);
			AssertEx(que.m_data, res);
		}
	};

	TEST_CLASS(P9029)
	{
		//【二分查找】P9029 [COCI 2022/2023 #1]  Čokolade|普及+		
		class Solution {
		public:
			vector<long long> Ans( const int N, vector<int>& c,vector<pair<int,int>>& km) {
				sort(c.begin(), c.end());
				vector<long long> preSum(N + 1);
				for (int i = 1; i <= N; i++) {
					preSum[i] = preSum[i - 1] + c[i-1];
				}
				vector<long long> ans;
				for (const auto& [K, M] : km) {
					const int& N1 = lower_bound(c.begin(), c.end(),K) - c.begin();
					const int& N2 = max(0, M - (N - N1));
					const int& N3 = min(N1, M);
					auto Check = [&](int mid) {
						if (N3 == mid) { return false; }
						return (c[mid] + c[N - (M - mid)] - 2*(long long)K) > 0;
					};
					auto M1 = CBinarySearch<int>(N2, N3).FindFrist(Check);
					const auto M2 = M - M1;
					long long cur = preSum[M1] - (preSum.back() - preSum[N - M2])+ (long long)K*2*M2;
					ans.emplace_back(cur);
				}		
				return ans;
			}
		};		
	public:
		int N;
		vector<int> c;
		vector<pair<int, int>> km;
		TEST_METHOD(TestMethod11)
		{
			N = 5, c = { 1,9,22,10,19 }, km = { {18,4},{5,2} };
			auto res = Solution().Ans(N,c,km);
			AssertEx({ 34,-21 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			N = 7, c = { 1,5,4,3,7,11,9 }, km = { {5,4},{5,7},{7,3},{4,5} };
			auto res = Solution().Ans(N, c, km);
			AssertEx({ 4,16,7,1 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			N = 3, c = { 5,6,7 }, km = { {10,1},{5,3},{3,3} };
			auto res = Solution().Ans(N, c, km);
			AssertEx({ 5,12,0 }, res);
		}
	};

	TEST_CLASS(P9124)
	{
		//【二分查找 寻找首端】P9124 [USACO23FEB] Bakery SP|普及+	
		class Solution {
		public:
			long long Ans(const long long TC,const long long TM,vector<tuple<long long,long long,long long>>& abc) {
				auto Check = [&](long long mid) {
					const auto K1 = TC + TM - mid;
					auto left = max(1LL, K1 - TM) ,r = min(TC, K1 - 1);
					for (const auto& [a, b, c] : abc) {
						const auto& K2 = c - b * K1;
						if (a == b) {
							if (K2 < 0) { return false; }
							continue;
						}
						if (a > b) {
							auto r1 = K2 / (a - b);
							r = min(r, r1);
						}
						else {
							auto left1 = K2 / (a - b) + (0 != K2%(a - b));
							left = max(left, left1);
						}
					}
					return r >= left;
				};
				return CBinarySearch<long long>(0, TC + TM - 2).FindFrist(Check);
			}
		};
	public:
		int TC,TM;
		vector<tuple<long long, long long, long long>> abc;
		TEST_METHOD(TestMethod11)
		{
			TC = 7, TM = 9, abc = { {4,3,18},{2,4,19},{1,1,6} };
			auto res = Solution().Ans(TC, TM, abc);
			AssertEx(11LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			TC = 7, TM = 3, abc = { {5,9,45},{5,2,31},{6,4,28},{4,1,8},{5,2,22} };
			auto res = Solution().Ans(TC, TM, abc);
			AssertEx(6LL, res);
		}
	};

	TEST_CLASS(P9178)
	{
		//【BFS 逆向思考】P9178 [COCI 2022/2023 #5] Diskurs|普及+
		class Solution {
		public:
			vector<int> Ans(const int M,const vector<int>& a) {
				const int MC = 1 << M;
				vector<vector<int>> neiBo(MC);
				for (int i = 0; i < MC;i++ ) {
					for (int j = 0; j < M; j++) {
						const int k = i ^ (1 << j);
						neiBo[i].emplace_back(k);
					}
				}
				vector<int> b(a.size());
				for (int i = 0; i < a.size(); i++) {
					b[i] = (~a[i]) & (MC - 1);
				}
				CBFSDis bfs(neiBo,b);
				vector<int> ans(a.size());
				for (int i = 0; i < a.size();i++ ) {
					ans[i] = M - bfs.m_vDis[a[i]];
				}
				return ans;
			}
		};
	public:		
		TEST_METHOD(TestMethod11)
		{			
			auto res = Solution().Ans(4, { 9,12,9,11 });
			AssertEx({ 2,3,2,3 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().Ans(4, { 5,7,3,9 });
			AssertEx({ 2,3,2,3 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().Ans(4, { 3,4,6,10 });
			AssertEx({ 3,3,2,3 }, res);
		}
	};

	TEST_CLASS(LC3733)
	{//【二分查找 容斥原理】3733. 完成所有送货任务的最少时间|分数未知
		class Solution {
		public:
			long long minimumTime(vector<int>& d, vector<int>& r) {
				const long long r1 = r[0], r2 = r[1];
				auto Check = [&](long long mid) {
					long long cnt3 = mid / lcm(r1, r2);//两无人机都充电
					long long cnt1 = mid / r1 - cnt3;//无人机一充电，无人机二不充电
					long long cnt2 = mid / r2 - cnt3;//无人机二充电，无人机一不充电
					long long cnt0 = mid - cnt3 - cnt1 - cnt2;//都不充电
					long long need = max(0LL, d[0] - cnt2) + max(0LL, d[1] - cnt1);
					return cnt0 >= need;
				};
				return CBinarySearch<long long>(0, 1e18).FindFrist(Check);
			}
		};
	public:
		vector<int> d, r;

		TEST_METHOD(TestMethod11)
		{
			d = { 3,1 }, r = { 2,3 };
			auto res = Solution().minimumTime(d, r);
			AssertEx(5LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			d = { 1,3 }, r = { 2,2 };
			auto res = Solution().minimumTime(d, r);
			AssertEx(7LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			d = { 2,1 }, r = { 3,4 };
			auto res = Solution().minimumTime(d, r);
			AssertEx(3LL, res);
		}

	};

	TEST_CLASS(LC3771)
	{//【逆序思考 堆 二分查找 前缀和】3771. 探索地牢的得分|分数未知
		class Solution {
		public:
			long long totalScore(int hp, vector<int>& damage, vector<int>& requirement) {
				const int N = damage.size();
				vector<long long> preSum(1);
				for (const auto& n : damage) {
					preSum.emplace_back(n + preSum.back());
				}
				long long ans = 0;
				for (int i = 0; i < N; i++) {
					long long val = requirement[i] + preSum[i + 1] -hp;
					int inx = lower_bound(preSum.begin(), preSum.begin() + i + 1, val)-preSum.begin();
					ans += i+1-inx;
				}
				return ans;
			}
		};
	public:
		int hp;
		vector<int>damage, requirement;
		TEST_METHOD(TestMethod11)
		{
			hp = 11, damage = { 3,6,7 }, requirement = { 4,2,5 };
			auto res = Solution().totalScore(hp, damage, requirement);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			hp = 2, damage = { 10000,1 }, requirement = { 1,1 };
			auto res = Solution().totalScore(hp, damage, requirement);
			AssertEx(1LL, res);
		}


	};
}




